package com.hyper_yang.algorithmRecord.June;
// 2025.06.01 给小朋友们分糖果
public class LeetCode_2929 {
/*
给你两个正整数 n 和 limit 。
请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。
     a + b + c = n
   0 ≤ a, b, c ≤ limit
 */

    /** 分给三位小朋友 An
     * @param: n - 糖果数量
     * @param: limit - 小朋友可获得的最大糖果数
     * return 总分法（总方案数）
     */
    // 方法一: 枚举
    public long distributeCandies1(int n, int limit) {
        long totalIdea = 0;
        // 排除极端情况
        if (n > limit * 3) return 0;
        if (n == limit * 3) return 1;
        for (int a = 0; a <= Math.min(n, limit); a++) {
            int minB = Math.max(0, n - a - limit);
            int maxB = Math.min(limit, n - a);
            if (minB <= maxB) {
                totalIdea += maxB - minB + 1;
            }
        }
        return totalIdea;
    }

    // 方法二: 动态规划
    public long distributeCandies2(int n, int limit) {
        // 排除极端情况
        if (n > limit * 3) return 0;
        if (n == limit * 3) return 1;
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int k = 1; k <= 3; k++) {
            long[] prefix = new long[n + 2];
            prefix[0] = 0;
            for (int i = 0; i <= n; i++) {
                prefix[i + 1] = prefix[i] + dp[i];
            }

            long[] newDp = new long[n + 1];
            for (int s = 0; s <= n; s++) {
                int minX = Math.max(0, s - limit);
                newDp[s] = prefix[s + 1] - prefix[minX];
            }
            dp = newDp;
        }

        return dp[n];
    }

    // 方法三: 数学公式法
    public long distributeCandies(int n, int limit) {
        // 排除极端情况
        if (n > limit * 3) return 0;  // 已经排除所有小朋友同时超出的情况
        if (n == limit * 3) return 1;
        return combination(n + 2) - 3 * combination(n - limit + 1) + 3 * combination(n - 2 * limit);
    }

    public long combination(long n) {
        return n > 1 ? (long) n * (n - 1) / 2 : 0;
    }

    public static void main(String[] args) {
        LeetCode_2929 solution = new LeetCode_2929();
        System.out.println(solution.distributeCandies(5,2)); // 3
        System.out.println(solution.distributeCandies(3,3)); // 10
    }
}
